package src.rumen.yi;

public class yi {
    public static void main(String[] args) {

    }
    //排序与异或运算

            //i==j时会出错
        public static void swap(int[] arr,int i,int j) { //交换arr i,j 位置上的值
            arr[i]=arr[i]^arr[j];
            arr[j]=arr[i]^arr[j];
            arr[i]=arr[i]^arr[j];
        }

        public static void selectionSort(int[] arr) { //选择排序  优于选择与冒泡排序
            if(arr == null || arr.length < 2) return;
            for (int i = 0; i <arr.length-1 ; i++) { //i~N+1
                int minIndex=i;
                for (int j = i+1; j <arr.length ; j++) { //i~N+1上找出最小值的下标
                    minIndex=arr[j]<arr[minIndex]?j:minIndex;
                }
                swap(arr,i,minIndex);
            }
        }

        public static void bubbleSort(int[] arr) { //冒泡排序
            if(arr==null||arr.length<2) return;
            for (int i = arr.length-1; i > 0 ; i--) {
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
                }
            }
        }

        public static void insertSort(int[] arr) { //插入排序
            if(arr==null||arr.length<2) return;
            for (int i = 1; i < arr.length ; i++) {//保证0~i有序
                for (int j = i; j > 0 && arr[j]<arr[j-1] ; j--) {
                    swap(arr,j,j-1);

                }

            }

        }

        //一个面试题：现有三种数字，两种出现偶数次，一种出现基数次，问：出现基数次的数字是？
        //^（亦或）的运算规律理解：@一：该位上，相同取0不同取1；@二：不进位加法；
        //^满足交换律，结合律;  0^a = a ; a^a = 0;
        public static void printOddTimesNumber1(int[] arr) {
            int eor=0;
            for (int i = 0; i <arr.length ; i++) {
                eor^=arr[i];
            }
            System.out.println(eor);
        }


        //再一个面试题：四种数字，两种出现基数次，两种出现偶数次，问出现基数次的两个数分别是？
        public static void printOddTimesNumber2(int[] arr) {
            int eor=0;
            for (int i = 0; i <arr.length ; i++) {
                eor^=arr[i];
                //此时eor=a^b;
                //取出eor二进制中最右边的一个1；此位置上a,b必然一个是0，一个是1；
                int rightOne=eor&(~eor+1);
                int one=0;
                for (int j = 0; j < arr.length ; j++) {
                    if((arr[j]&rightOne)==0/*或者1*/) one^=arr[i];//得到a或b
                }
                System.out.println(one+" "+(eor^one));
            }
        }
}